package day230414;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/15 16:58
 * 微信红包
 */
public class Gift {
    // 返回出现次数为红包个数一半以上的金额, 如果不存在则返回0
    public int getValue(int[] gifts, int n) {
        // 众数思想, 假定数组中第一个元素值为众数, 迭代次数, 相同自增, 不同自减, 直到为0替换到下一个数
        int value = gifts[0]; // 记录可能的众数
        int countValue = 1; // 记录数字出现的次数
        for (int i = 1; i < gifts.length; i++) {
            if (gifts[i] == value) {
                countValue++;
            } else {
                countValue--;
            }
            if (countValue == 0) {
                // 更新众数和次数
                value = gifts[i];
                countValue = 1;
            }
        }
        // value 可能为众数, 只需要判断是否出现数组长度的一半即可
        countValue = 0;
        for (int gift : gifts) {
            if (value == gift) {
                countValue++;
            }
        }
        if (countValue > n / 2) {
            return value;
        }
        return 0;
    }
}
